// 生成avl树
var nil = { key: 0, h: 0, left: null, right: null };
class Node {
  constructor(key = 0, h = 0, left = nil, right = nil) {
    this.key = key;
    this.h = h;
    this.left = left;
    this.right = right;
  }
}

// 生成一个新节点
function getNewNode(key) {
  return new Node(key, 1);
}

// 更新节点高度
function update_heigth(root) {
  root.h = Math.max(root.left.h, root.right.h) + 1;
}

// 左旋
function left_rotate(root) {
  let new_root = root.right;
  root.right = new_root.left;
  new_root.left = root;
  update_heigth(root);
  update_heigth(new_root);
  return new_root;
}

// 右旋
function right_rotate(root) {
  let new_root = root.left;
  root.left = new_root.right;
  new_root.right = root;
  update_heigth(root);
  update_heigth(new_root);
  return new_root;
}

// 四种失衡类型
const TYPE_STR = ["", "LL", "RR", "LR", "RL"];

// 失衡之后的调整操作
function maintain(root) {
  if (Math.abs(root.left.h - root.right.h) < 2) return root;
  let type = -1,
    val = root.key;
  if (root.left.h > root.right.h) {
    if (root.left.right.h > root.left.left.h) {
      console.log("left rotate", root.left.key);
      root.left = left_rotate(root.left);
      type = 3;
    }
    console.log("right rotate", val);
    root = right_rotate(root);
    if (type == -1) type = 1;
  } else {
    if (root.right.left.h > root.right.right.h) {
      console.log("right rotate", root.right.key);
      root.right = right_rotate(root.right);
      type = 4;
    }
    console.log("left rotate", val);
    root = left_rotate(root);
    if (type == -1) type = 3;
  }
  console.log("maintain type", TYPE_STR[type - 1]);
  return root;
}

// 清空树
function clear(root) {
  if (root == null) return;
  delete root.left;
  delete root.right;
}

// 树的插入操作
function insert(root, key) {
  if (root == nil) return getNewNode(key);
  if (root.key == key) return root;
  if (key < root.key) root.left = insert(root.left, key);
  else root.right = insert(root.right, key);
  update_heigth(root);
  return maintain(root);
}

// 寻找一个节点的前驱
function predeccessor(root) {
  let tmp = root.left;
  while (tmp.right != nil) tmp = tmp.right;
  return tmp;
}

// 删除树的指定节点
function erase(root, key) {
  if (root == nil) return root;
  if (key < root.key) root.left = erase(root.left, key);
  else if (key > root.key) root.right = erase(root.right, key);
  else {
    if (root.left == nil || root.right == nil) {
      let tmp = root.left == nil ? root.left : root.right;
      return tmp;
    } else {
      let tmp = predeccessor(root);
      root.key = temp.key;
      root.left = erase(root.left, tmp.key);
    }
  }
  update_heigth(root);
  return maintain(root);
}

function func(arr) {
  let n = nil;
  arr.forEach((v) => {
    n = insert(n, v);
    console.log(
      "-----------------avl tree start------------------\n",
      JSON.stringify(n, " ", 2),
      "-----------------avl tree end------------------\n",
    );
  });
}
let arr = [1, 2, 3, 4];
let arr2 = [5, 9, 8, 3, 2, 4, 1, 7];
func(arr2)
